package newcoder_exp.justPractise;
import java.util.*;

import org.junit.Test;

import tree.*;
public class Nc94 {
    public class Solution {
        /**
         * 
         * @param root TreeNode类 the root of binary tree
         * @return int整型二维数组
         */
        public int[][] threeOrders (TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root, prev = null;
            List<Integer> pre = new ArrayList<>();
            List<Integer> in = new ArrayList<>();  
            List<Integer> post = new ArrayList<>();
            
            stack.push(root);
            while (!stack.isEmpty()) {
                cur = stack.pop();
                pre.add(cur.val);
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
            cur = root;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                in.add(cur.val);
                cur = cur.right;
            }
            
            cur = root;
            while (cur != null || !stack.isEmpty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.peek();
                if (cur.right != null && cur.right != prev) {
                    cur = cur.right;
                } else {
                    cur = stack.pop();
                    post.add(cur.val);
                    prev = cur;
                    cur = null;
                }
            }
            post.clear();
            Stack<Integer> help = new Stack<>();
            stack.push(root);
            while (stack.size() != 0) {
                cur = stack.pop();
                help.push(cur.val);
                if (cur.left != null) stack.push(cur.left);
                if (cur.right != null) stack.push(cur.right);
            }
            while (!help.isEmpty()) {
                post.add(help.pop());
            }
            res.add(pre);
            res.add(in);
            res.add(post);
            int[][] result = new int[3][];
            for (int i = 0; i < res.size(); i++) {
                result[i] = res.get(i).stream().mapToInt(Integer::valueOf).toArray();
            }
            return result;
        }
    }

    @Test
    public void test() {
        TreeNode root = TreeUtils.createTree(new Integer[]{1,2,3});
        Solution s = new Solution();
        int[][] res = s.threeOrders(root);
        System.out.println(Arrays.deepToString(res));
    }
}
